package com.demo.leetcode;

import java.util.TreeSet;

/**
 * 存在重复元素 III
 */
public class leetcode220 {
    /**
     * 给定一个整数数组，判断数组中是否有两个不同的索引 _i_ 和 _j_ ，使得 nums [i] 和 nums [j] 的差的绝对值最大为 _t_ ，并且 _i_ 和 _j_ 之间的差的绝对值最大为 _ķ_ 。
     * 示例 1:
     * 输入: nums = [1,2,3,1], k  = 3, t = 0
     * 输出: true
     * 示例 2:
     * 输入: nums = [1,0,1,1], k  =  1, t = 2
     * 输出: true
     * 示例 3:
     * 输入: nums = [1,5,9,1,5,9], k = 2, t = 3
     * 输出: false
     */
    public static boolean test(int nums[], int k, int t) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (Math.abs(nums[i] - nums[j]) == t && Math.abs(i - j) == k) {
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Integer> set = new TreeSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            Integer s = set.ceiling(nums[i]);//take the smallest greater number than nums[i] is there exists
            if (s != null && s - nums[i] <= t) {
                return true;//it must be s - nums[i] here, otherwise, cases like [4,2] 2, 1 wont' pass, because we'll get 2-4 = -2 which is a negative number that for sure will be smaller than t
            }
            Integer g = set.floor(nums[i]);//take the biggest smaller number than nums[i] if there exists
            if (g != null && (long) nums[i] - g <= t) {
                return true;
            }
            set.add(nums[i]);
            if (set.size() > k) {
                set.remove(nums[i - k]);//set doesn't have indices and it's not ordered, we could only specify the element
                //that we want to remove, this element is nums[i-k]
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 1};
        int k = 3;
        int t = 0;
        boolean test = test(nums, k, t);
        boolean b = containsNearbyAlmostDuplicate(nums, k, t);
        System.out.println(test);
        System.out.println(b);
    }
}
